import java.util.Arrays;

public class Solution1029 {
    public int twoCitySchedCost(int[][] costs) {
        int[][] f=new int[costs.length/2+1][costs.length/2+1];
        for (int i=0;i<=costs.length/2;i++){
            Arrays.fill(f[i],Integer.MAX_VALUE/3);
        }
        f[0][0]=0;
        for (int[] cost : costs) {
            int[][] g=new int[costs.length/2+1][costs.length/2+1];
            for (int i=0;i<=costs.length/2;i++){
                for (int j=0;j<=costs.length/2;j++){
                    g[i][j]=f[i][j];
                }
            }
            for (int i=0;i<=costs.length/2;i++){
                for (int j=0;j<=costs.length/2;j++){
                    if (i>0){
                        f[i][j]=Math.min(f[i][j],g[i-1][j]+cost[0]);
                    }
                    if (j>0){
                        f[i][j]=Math.min(f[i][j],g[i][j-1]+cost[1]);
                    }
                }
            }
        }
        return f[costs.length/2][costs.length/2];
    }

    public static void main(String[] args) {
        System.out.println(new Solution1029().twoCitySchedCost(new int[][]{{10,20},{30,200},{400,50},{30,20}}));
    }
}
